//给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 
//values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 
//
// 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj =
// ? 的结果作为答案。 
//
// 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替
//代这个答案。 
//
// 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。 
//
// 
//
// 示例 1： 
//
// 
//输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"]
//,["b","a"],["a","e"],["a","a"],["x","x"]]
//输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
//解释：
//条件：a / b = 2.0, b / c = 3.0
//问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
//结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
// 
//
// 示例 2： 
//
// 
//输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], 
//queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
//输出：[3.75000,0.40000,5.00000,0.20000]
// 
//
// 示例 3： 
//
// 
//输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],[
//"a","c"],["x","y"]]
//输出：[0.50000,2.00000,-1.00000,-1.00000]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= equations.length <= 20 
// equations[i].length == 2 
// 1 <= Ai.length, Bi.length <= 5 
// values.length == equations.length 
// 0.0 < values[i] <= 20.0 
// 1 <= queries.length <= 20 
// queries[i].length == 2 
// 1 <= Cj.length, Dj.length <= 5 
// Ai, Bi, Cj, Dj 由小写英文字母与数字组成 
// 
// Related Topics深度优先搜索 | 广度优先搜索 | 并查集 | 图 | 数组 | 最短路 
//
// 👍 830, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

class EvaluateDivision {
    public static void main(String[] args) {
        Solution solution = new EvaluateDivision().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 带权的并查集
        // https://leetcode.cn/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            int equationsSize = equations.size();
            UF uf = new UF(equationsSize * 2);
            Map<String, Integer> map = new HashMap<>(2 * equationsSize);
            int id = 0; // id，表示节点的编号
            for (int i = 0; i < equationsSize; i++) {
                List<String> equation = equations.get(i);
                String var1 = equation.get(0);
                String var2 = equation.get(1);

                if (!map.containsKey(var1)) {
                    map.put(var1, id);
                    id++;
                }

                if (!map.containsKey(var2)) {
                    map.put(var2, id);
                    id++;
                }

                // 加入并查集
                uf.union(map.get(var1), map.get(var2), values[i]);
            }

            // 查询结果
            int querySize = queries.size();
            double[] res = new double[querySize];
            for (int i = 0; i < queries.size(); i++) {
                List<String> query = queries.get(i);
                String var1 = query.get(0);
                String var2 = query.get(1);
                if (!map.containsKey(var1) || !map.containsKey(var2)) {
                    res[i] = -1.0d;
                } else {
                    res[i] = uf.connected(map.get(var1), map.get(var2));
                }
            }

            return res;
        }

        // 带权重的并查集
        // 并查集的基本框架：https://labuladong.gitee.io/algo/2/22/53/
        class UF {
            private int[] parent;
            private double[] weight;   // 指向父节点的权重，weight[i]表示i到根节点的权重

            public UF(int n) {
                this.parent = new int[n];
                this.weight = new double[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                    weight[i] = 1.0d;
                }
            }

            public void union(int x, int y, double value) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX == rootY) {
                    return;
                }

                // 连接两个根节点
                parent[rootX] = rootY;

                // 需要更新rootX指向根节点rootY的权重
                weight[rootX] = (weight[y] * value) / weight[x];
            }

            public double connected(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX == rootY) {
                    // 有连通
                    return (double) weight[x] / weight[y];
                } else {
                    // 不连通直接返回
                    return -1.0d;
                }
            }

            public int find(int x) {
                // 路径压缩
                if (parent[x] != x) {
                    int origin = parent[x];
                    parent[x] = find(find(parent[x]));
                    // 路径压缩之后，当前节点权重 = 当前节点到上一个的权重 * 上一个节点到根节点的权重
                    weight[x] *= weight[origin];
                }
                return parent[x];
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
